package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 1969. 数组元素的最小非零乘积
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/5 14:30
 */
public class MinNonZeroProduct {

    private int mod = 1000000007;

    public int minNonZeroProduct(int p) {
        long n = (1L << (p - 1)) - 1;
        long num = (1L << p) - 1;
        long res = multiply(num - 1, n) % mod;
        return (int) ((res * (num % mod)) % mod);
    }

    private long multiply(long base, long k) {
        long res = 1;
        while (k != 0) {
            if (k % 2 == 1) {
                res = ((res % mod) * (base % mod)) % mod;
            }
            base = ((base % mod) * (base % mod)) % mod;
            k /= 2;
        }
        return res;
    }

}
